package com.wkh.datastructure.RedAndBlack;

/**
 * 红黑树
 */
public class RedBlackTree {
    //颜色的枚举类
    enum Color{
        RED,
        BLACK
    }
    //根节点
    private static Node root;
    private static class Node{
        int key;
        Object value;
        Node left;
        Node right;
        //该节点的父节点
        Node parent;
        Color color = Color.RED;

        public Node(int key, Object value) {
            this.key = key;
            this.value = value;
        }

        public Node(int key, Object value, Node left, Node right) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
        }

        //判断是否是左孩子
        private boolean isLeftChild(){
            return parent != null && parent.left == this;
        }
        //寻找叔叔节点
        private Node uncle(){
            if(parent == null || parent.parent == null){
                return null;
            }else if (parent.isLeftChild()){
                return parent.parent.right;
            }else{
                return parent.parent.left;
            }
        }
        //寻找兄弟节点
        private Node sibling(){
            if (parent == null){
                return null;
            }else if (this.isLeftChild()){
                return parent.right;
            }else{
                return parent.left;
            }
        }
        //判断节点的颜色
        private boolean isRed(Node node){
            return node != null && node.color == Color.RED;
        }
        private boolean isBlack(Node node){
            return node == null || node.color == Color.BLACK;
        }

        /**
         * 1.parent的处理
         * 2.新根的父子关系
         * @param pink
         */
        //右旋
        private void rightRotate(Node pink){
            Node parent = pink.parent;
            Node yellow = pink.left;
            Node green = yellow.right;
            yellow.right = pink;
            pink.left = green;
            //parent的处理
            yellow.parent = parent;
            pink.parent = yellow;
            if (green != null){
                green.parent = pink;
            }
            //新根的父子关系
            if (parent == null){
                root = yellow;
            }
            if (parent.left == pink){
                parent.left = yellow;
            }else{
                parent.right = yellow;
            }
        }

        //左旋
        private void leftRotate(Node pink){
            Node parent = pink.parent;
            Node yellow = pink.right;
            Node green = yellow.left;
            yellow.left = pink;
            pink.right = green;
            //parent的处理
            yellow.parent = parent;
            pink.parent = yellow;
            if (green != null){
                green.parent = pink;
            }
            //新根的父子关系
            if (parent == null){
                root = yellow;
            }
            if (parent.left == pink){
                parent.left = yellow;
            }else{
                parent.right = yellow;
            }
        }
        //put 新增或更新
        public void put(int key ,Object value){
            Node p = RedBlackTree.root;
            Node parent = null;
            while (p!=null){
                parent = p;
                if (key<p.key){
                    p = p.left;
                }else if (key>p.key){
                    p = p.right;
                }else{
                    //更新
                    p.value = value;
                    return;
                }
            }
            //新增
            Node insertNode = new Node(key, value);
            if (parent == null){
                root = insertNode;
            }else if (parent.key < key){
             parent.right = insertNode;
             insertNode.parent = parent;
            }else if (parent.key>key){
                parent.left = insertNode;
                insertNode.parent = parent;
            }
            fixRedRed(insertNode);
        }
        //调正节点,两个相邻的红色节点
        private void fixRedRed(Node x){
            //case1:插入节点是根节点
            if (x == root){
                x.color = Color.RED;
                return;
            }
            //case2:插入节点的父亲是黑色
            if (isBlack(x)){
                return;
            }
            //case3:插入节点的父亲为红色，红红相邻时
            /**
             * 1.父亲变为黑色，为了保证黑色平衡，连带的叔叔也变为黑色
             * 2.祖父如果是黑色不变，会造成这颗子树黑色过多，因此祖父节点变为红色
             * 3.祖父如果变成红色，可能会接着触发红红相邻，因此对将祖父进行递归调整
             */
            Node parent = x.parent;
            Node uncle = x.uncle();
            Node grandparent = parent.parent;
            if (isRed(uncle)){
                parent.color = Color.BLACK;
                uncle.color = Color.BLACK;
                grandparent.color = Color.RED;
                //递归调用
                fixRedRed(grandparent);
                return;
            }
            //case4:叔叔为黑色
            /**
             * 1.父亲为左孩子，插入节点也是左孩子，此时即LL不平衡
             */
            if (parent.isLeftChild() && x.isLeftChild()){
                parent.color = Color.BLACK;
                grandparent.color = Color.RED;
                //右旋
                rightRotate(grandparent);
            }
            /**
             * 2.父亲为左孩子，插入节点是右孩子，此时即LR不平衡
             */
            if (parent.isLeftChild() && !x.isLeftChild()){
                leftRotate(parent);//先左旋
                x.color = Color.BLACK;//变色
                grandparent.color = Color.RED;//变色
                rightRotate(grandparent);//再右旋
            }
            /**
             * 3.父亲为右孩子，插入节点也是右孩子，此时即RR不平衡
             */
            if (!parent.isLeftChild() && !x.isLeftChild()){
                parent.color = Color.BLACK;
                grandparent.color = Color.RED;
                //左旋
                leftRotate(grandparent);
            }
            /**
             * 4.父亲为右孩子，插入节点也是左孩子，此时即RL不平衡
             */
            if (!parent.isLeftChild() && x.isLeftChild()){
                rightRotate(parent);//先右旋
                x.color = Color.BLACK;//变色
                grandparent.color = Color.RED;//变色
                leftRotate(grandparent);//再左旋
            }
        }
    }

}
